package bTree.LeetCode;

import java.util.LinkedList;
import java.util.List;

public class 复原ip地址 {
    List<String>res=new LinkedList<>();
    int pointnum=0;
    public List<String> restoreIpAddresses(String s) {
        backtraking(s,0);
        return res;
    }

    private void backtraking(String s, int startindex) {
        if(pointnum==3){
            if(isvalue(s.substring(startindex,s.length()))){
                res.add(s);
            }
            return;
        }
        for(int i=startindex;i<s.length()-1;i++){
            if(isvalue(s.substring(startindex,i+1))){
                s=s.substring(0,i+1)+'.'+s.substring(i+1);
                pointnum++;
                backtraking(s,i+2);
                pointnum--;
                s=s.substring(0,i+1)+s.substring(i+2);
            }else{
                return;
            }
        }
    }

    private boolean isvalue(String substring) {
        if(substring.startsWith("0")&&substring.length()>1){
            return false;
        }
        if(Long.parseLong(substring)>255){
            return false;
        }
        for (int i=0;i<substring.length();i++){
            if(substring.charAt(i)>'9'||substring.charAt(i)<'0'){
                return false;
            }
        }
        return true;
    }
}